package com.scott.ch040;

/**
 * @author 黄后林
 * @version 1.0
 * @note  希尔排序算法
 * @date 2022-03-11 18:32:44
 */
public class Shell {

    /**
     * 方法描述: 对数组array的元素进行希尔排序
     * @author: 黄后林
     * @date: 2022/3/11 18:33
     * @param array
     */
    public static void sort(Comparable[] array){

        // 1、根据数组array的长度确定增长量h的初始值
        int h =init(array);

        // 2、进行希尔排序
        while(h>=1){
            // 2.1 排序
                //2.1.1 找到待插入的元素所在的下标index  第1个待插入的元素= h所在的下标
                for(int index=h;index<array.length;index++){

                    for(int j=index;j>=h;j=j-h){ // 第1个待插入的元素= h所在的下标
                        //2.1.2 把待插入的元素插入到有序序列中

                        // 待插入的元素是a[j]、 比较a[j]和a[j-h]
                        if(greater(array[j-h],array[j])){
                            // 说明前面的数比后面的数大  交换位置
                            exchange(array,j-h,j);

                        }else{
                            // 说明前面的数比后面的数小  不动=结束循环
                            break;
                        }
                    }
                }

            // 2.2 减少h的值
            h=h/2;
        }

    }


    /**
     * 方法描述: 根据数组array的长度确定增长量h的初始值
     * @author: 黄后林
     * @date: 2022/3/11 18:51
     * @param array
     * @return int 增长量的初始值
     */
    private static  int init(Comparable[] array){
        int h =1;
        while(h<array.length/2){
            h=2*h+1;
        }

        System.out.println("h=[ "+h+" ]");
        return h;
    }


    /**
     * 方法描述:
     * @author: 黄后林
     * @date: 2022/3/11 18:42
     * @param first   第1个元素
     * @param second  第2个元素
     * @return true代表第1个元素比第2个元素大
     */
    private static boolean greater(Comparable first, Comparable second){
        // 如果first和second大   那么rs=1
        // 如果first和second小   那么rs=-1
        // 如果first和second相等 那么rs=0
        int rs=  first.compareTo(second);
        System.out.println(rs);
        return rs>0;
    }

    /**
     * 方法描述: 下标为indexFirst的元素和下标为indexSecond的元素交换位置
     * @author: 黄后林
     * @date: 2022/3/11 18:41
     * @param array  数组
     * @param indexFirst  第1个元素的下标
     * @param indexSecond 第2个元素的下标
     */
    private static void exchange(Comparable[] array, int indexFirst, int indexSecond){

        Comparable tmp;
        tmp=array[indexFirst];
        array[indexFirst]=array[indexSecond];
        array[indexSecond]=tmp;
    }
}
